/**
 * 给定一个二叉树的根节点 root，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 *
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 *https://leetcode.cn/problems/path-sum-iii/
 * 思路：递归穷举所有可能
 */
class PathSumThreeQoJu {
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null){
            return 0;
        }
        int ret=sumPath(root,targetSum);
        ret+=pathSum(root.left,targetSum);
        ret+=pathSum(root.right,targetSum);
        return ret;
    }
    public int sumPath(TreeNode root,int targetSum){
        if(root==null){
            return 0;
        }
        int ret=0;
       targetSum=targetSum-root.val;
        if(targetSum==0){
            ret++;
        }
        ret+=sumPath(root.left,targetSum);
        ret+=sumPath(root.right,targetSum);
        return ret;
    }
}